// 凸包算法
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct point
{
	double x, y;
};
point p0;
double angle(const point *a, point p)
{
	return (a->x - p.x) / sqrt((a->x - p.x) * (a->x - p.x) + (a->y - p.y) * (a->y - p.y));
}
// 极角排序
int compare(const void *a, const void *b)
{
	double k1 = angle(((const point *)a), p0);
	double k2 = angle(((const point *)b), p0);
	if (k1 > k2)
		return -1;
	else if (k1 == k2)
		return 0;
	else
		return 1;
}
double get_rotaion(point p1, point p2, point p3)
{
	return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.x * p3.y - p2.x * p1.y - p3.x * p2.y;
}
void Graham(point set[], int n)
{
	// 1.找出y最小的点
	int min = 0;
	for (int i = 0; i < n; i++)
	{
		if (set[i].y < set[min].y)
		{
			min = i;
		}
	}
	p0 = set[min];
	// 2.进行极角排序
	qsort(set + 1, n - 1, sizeof(point), compare);
	// 3.遍历
	point stack[20];
	int top = -1;
	stack[++top] = set[n - 1];
	stack[++top] = set[0];
	int i = 1;
	while (i < n - 1)
	{
		point p1, p2, p3;
		p1 = stack[top - 1];
		p2 = stack[top];
		p3 = set[i];
		// >0 则左旋入栈
		if (get_rotaion(p1, p2, p3) > 0)
		{
			stack[++top] = p3;
			i++;
		}
		// 否则退栈 包含==0的情况
		else
		{
			top--;
		}
	}

	for (int i = 0; i <= top; i++)
	{
		printf("<%3.2lf,%3.2lf>", stack[i].x, stack[i].y);
	}
}
int main()
{
	/*******************code*******************/
	// 1.找出y最小的点
	point set[7];
	p0.x = p0.y = 0;
	set[0].x = 0;
	set[1].x = 4;
	set[2].x = 1;
	set[3].x = 1;
	set[4].x = 3;
	set[5].x = -2;
	set[6].x = -4;
	set[0].y = 0;
	set[1].y = 1;
	set[2].y = 1;
	set[3].y = 5;
	set[4].y = 2;
	set[5].y = 4;
	set[6].y = 1;
	int n = 7;

	Graham(set, n);

	/******************************************/
	printf("\n\n****************************\n");
	printf("Press Enter key to continue\n");
	getchar();
	return 0;
	/******************************************/
}
